package 算法模板;

/**
 *
 */
public class 字典树 {

    public static void main(String[] args) {

    }

}

/**
 * 并不需要为对象创建一个value属性
 * 由于仅由小写字母组成，其子孩子用一个26个trie节点的数组来存储，
 * 如果curNode==null，那么不存在
 */
class Trie {

    public boolean end;

    public Trie[] children;

    public Trie() {
        children = new Trie[26];
    }

    public void insert(String word) {
        char[] letters = word.toCharArray();
        Trie curTree = this;

        for (int i = 0; i < letters.length; i++) {
            int index = letters[i] - 'a';
            // 当前树层的字母没有对应的字符
            if (curTree.children[index] == null) {
                curTree.children[index] = new Trie();
            }
            curTree = curTree.children[index];
        }
        // 最后一个字母需要做标记
        curTree.end = true;
    }

    public boolean search(String word) {
        Trie lastTree = findLastTree(word);
        return lastTree != null && lastTree.end;
    }

    public boolean startsWith(String prefix) {
        return findLastTree(prefix) != null;
    }

    /**
     * 查询是否有单词的开始到单词的结束全部字母
     * 如果有返回最后一个字母对象
     *
     * @return
     */
    public Trie findLastTree(String prefix) {
        char[] letters = prefix.toCharArray();
        Trie curTree = this;
        for (int i = 0; i < prefix.length(); i++) {
            Trie nextTree = curTree.children[letters[i] - 'a'];
            if (nextTree == null) {
                return null;
            }
            curTree = nextTree;
        }
        return curTree;
    }
}